L-RCM: a method to detect connected components in undirected graphs by using the Laplacian matrix and the RCM algorithm

摘要

In this paper we consider undirected graphs with no loops and multiple edges,consisting of k connected components. In these cases, it is well known that onecan find a numbering of the vertices such that the adjacency matrix A is blockdiagonal with k blocks. This also holds for the (unnormalized) Laplacian matrixL= D-A, with D a diagonal matrix with the degrees of the nodes. In this paperwe propose to use the Reverse Cuthill-McKee (RCM) algorithm to obtain a blockdiagonal form of L that reveals the number of connected components of thegraph. We present some theoretical results about the irreducibility of theLaplacian matrix ordered by the RCM algorithm. As a practical application wepresent a very efficient method to detect connected components with acomputational cost of O(m+n), being m the number of edges and n the number ofnodes. The RCM method is implemented in some comercial packages like MATLAB andMathematica. We make the computations by using the function symrcm of MATLAB.Some numerical results are shown